#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2022, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 226. 翻转二叉树.py
@time: 2022/1/28 16:26
@desc: https://leetcode-cn.com/problems/invert-binary-tree/
> 给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
@解题思路：
    1. 递归, Ot(N), Os(N)
'''
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def invertTree(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        if not root: return None
        left = self.invertTree(root.left)
        right = self.invertTree(root.right)
        root.left, root.right = right, left
        return root